1. Field of the Invention
The present invention relates to a picture image storing method and device for storing picture image information in a large-capacity memory device. The picture information is compressed through the processing of its redundancy from the viewpoint of information theory.
2. Discussion of the Related Art
In recent years, along with the ever-increasing use of personal computer systems and word processors, the type and quantity of picture image information produced by copying and other similar processes has increased dramatically. Copying machines are now required to not only attain higher picture quality, but to also perform functions in addition to merely producing a prescribed number of copies of an original document or producing enlarged-scale or reduced-scale copies of the original document.
The various additional functions now required of copying machines will be described. An electronic recirculating document handler (RDH) electronically performs the operation of producing an arbitrarily selected number of properly sorted copies of a number of sheets in an original document. A book-binding function produces properly bound copies with the picture images of an original document edited and copied on them. In the book-binding function, two pages of the original are copied onto a single page, and the copied pages are put together, stapled in the center, folded into halves, and bound into a booklet with the copied sheets arranged as in the original document. Additionally, the functions required of copying machines include communicating picture images. Copy machines do the work of facsimile machines, and computer printers.
Digital copying machines can perform the functions required of a new copy machine. Specifically, the digital copying machine transports the individual sheets of an original document, in their regular sequential order, to the area over the platen of the copying machine by an automatic transporting process with an automatic document feeder (ADF). The original document is set, and then a scanner reads the picture images on the original document. The picture images are converted into digital signals, and temporarily stored. The copying machine then reads out the stored picture image information and prints the copies with an image output terminal (hereinafter called "IOT").
The digital copying machine also communicates picture images, and performs as a facsimile machine and a computer printer. The digital copying machine receives, in parallel through an input interface and a multiplexer, picture image information over a telephone line from a facsimile machine, a host computer, or a personal computer system in addition to the picture image information from the scanner.
The digital copying machine stores the picture image information received through the input interface from a facsimile machine, a host computer, or a personal computer system. The copying machine records the picture images at the IOT after reading the stored picture image information out of the storage device.
The digital copying machine employs a picture image storage device, which stores the picture image information in a compressed state. The data compression is achieved by reducing information redundancy, as viewed from the standpoint of information theory. Because of data compression, a larger amount of picture image information may be stored.
As shown in FIG. 15, a compressing device 101 in the picture image storing device compresses the picture image information from a scanner 100. A large-capacity storage device 102, which is composed preferably of a hard disk, stores the compressed information.
The image information transfer rate between the scanner 100 and the compressing device 101 is on the order of approximately 1 mega byte per second, which is faster than the transfer rate of the storage device 102. Therefore, if the picture image information compressed by the compressing device 101 is transferred unchanged to the storage device 102, it will not be possible to store the compressed picture image information in the storage device 102. For this reason, a page buffer, which temporarily stores the picture image information by the page, is provided between the compressing device 101 and the storage device 102. The picture image information, transferred from the compressing device 101, is stored in page units in the page buffer 103. Then, the picture image information stored temporarily in the page buffer 103 is transferred to the storage device 102 at the transfer rate of the storage device 102.
After all the picture image information of an original document is stored in the storage device 102, the picture image information stored in the storage device 102 is read out in page units at a prescribed timing. The picture image information read out of the storage device 102 is written to the page buffer 103. When all the picture image information for one page is stored in the page buffer 103, the picture image information is decoded in its regular sequence by an extending device 104, and output to the IOT 105.
The picture image storing device stores picture image information from the original document in the storage device 102 by reducing the amount of picture image information. The picture image information is encoded in the state with its redundancy as viewed from the standpoint of information theory, and compressed by means of the compressing device 101. A known encoding process generally called "the Block Truncation Coding Process" is disclosed in Japanese Laid Open Patent No. 69505-1981 (JP 69505), the contents of which are herein incorporated by reference.
The encoding process of JP 69505 encodes the picture image information of an original document, read and converted into digital signals by a scanner, by first dividing the digital signals into blocks of L.times.L pixels. When the density of the individual pixels in a block is taken as a.sub.ij for each pixel, the average picture image density pO in the block may be expressed as: pO=.SIGMA.a.sub.ij / L.sup.2. The individual pixels within the block are divided between those pixels having a density higher than the average picture image density pO and those pixels having a density lower than the average picture image density pO.
The average density of the pixels having a density lower than the average picture image density pO can be expressed as p1 by the equation p1=.SIGMA.a.sub.ij /Nl, where Nl is the number of pixels having a density lower than pO and .SIGMA. is set for a.sub.ij .ltoreq.pO. The number Nl of the pixels having a density lower than the average picture image density pO can be expressed by the equation Nl=.SIGMA..PHI..sub.ij, where .PHI. is a variable that assumes the value 1 when the density of a.sub.ij .ltoreq.pO and assumes the value 0 when the density of a.sub.ij &gt;pO.
The average density of the pixels having a density higher than the average picture image density pO can be expressed as p2 by the equation p2=.SIGMA.a.sub.ij /N2, where N2 is the number of pixels having a density higher than pO and .SIGMA. is set for a.sub.ij &gt;pO. The number N2 of pixels having a density higher than the average picture image density pO can be expressed by the equation N2=.SIGMA..PHI..sub.ij, where .PHI..sub.ij is a variable that assumes the value 0 when a.sub.ij .ltoreq.pO and assumes the value 1 when a.sub.ij &gt;pO.
Integral numbers m and n are respectively smaller than the number of pixels L.sup.2 in the block, and the number of chromatic grades in the density of the individual pixels. The integral number m is a parameter for deciding the magnitude of the absolute value of p1-p2 which expresses the difference between the average picture image density values p1 and p2. The integral number n is a parameter for deciding the magnitude of the numbers of pixels Nl and N2.
When p1-p2&lt;m or nl&lt;n or n2&lt;n is true, the distribution of density within the block is considered uniform, and, with all the values of .PHI..sub.ij taken as 0, only the average picture image density pO is used to represent the picture images within the block. As the result of this operation, the picture images within the block can be expressed by .PHI..sub.ij, which is used as the resolution information composed entirely of the value 0 in all cases, and the average picture image density pO is used as the chromatic gradation information.
However, when p1-p2.gtoreq.m and nl.gtoreq.n and n2.gtoreq.n holds true, the distribution of density within the block is considered not uniform, and .PHI..sub.ij is used as the resolution information, while the average density values p1 and p2 are used as the chromatic gradation information. The number p1 is designated as the chromatic gradation information for the pixels which have the value 0 for the .PHI..sub.ij, namely, a density value equal to or less than the average image density pO. The number `is designated as the chromatic gradation information for the pixels which have the value 1 for the .PHI..sub.ij, namely, a density value higher than the average picture image density. The picture image information within the block is expressed in terms of an .PHI..sub.ij which has the values of 0 or 1 as the resolution information and the average density values p1 and p2 as the chromatic gradation information.
The picture image information from the original document is processed for compression by encoding the picture image information within a block. The block is expressed, by an existing binary value encoding process, with the resolution information .PHI..sub.ij being put together for several lines. The length of the consecutive blocks having the same information are encoded by an existing run length encoding process.
The parameter m is a deciding value for the removal of isolated noises in the picture images, and the parameter n is a deciding value for the removal of delicate fluctuations in the density within a block. Thus, the parameters m and n are directly proportional to the uniformity of the picture images within the block.
The electronic recirculating document handler function produces an arbitrarily selected number of properly sorted copies of a number of sheets of an original document. In order to realize the electronic recirculating document handler function with picture image storing device operating by a picture image coding process, the picture image information on a plurality of sheets of the original document, are stored in regular sequence and stored in a compressed state in the storage device 102 by way of the page buffer 103. The compressed picture image information is read out in page units, in regular sequence and decoded in regular sequence by the extending device 104. The decoded picture image information is recorded in the regular sequence of the pages by the IOT 105. The device can produce an arbitrarily decided number of properly sorted copies of a number of sheets the original document by repeating the operations of reading the picture image information of the original document out of the IOT 105 and recording the picture image information with the IOT 105 a number of times corresponding to the number of copies desired.
The known copying machine described above has the following disadvantages.
The picture image storing device 102 temporarily stores picture image information after the picture image information is compressed by the picture image encoding process performed by the compressing device 101. The storage device 102 has a limited memory capacity. Therefore, in the realization of the electronic recirculating document handler function, the remaining capacity of the storage device 102 may be reduced to zero when an attempt is made, while the storage device 102 has a small memory capacity left, to store the compressed picture image information read an original document. Additional picture image information may not be stored in the storage device 102. Any attempt to store additional picture image information into the storage device 102 will result in defects by page units in some part of a series of sheets of the original document. Therefore, reading original documents with the scanner 100 is discontinued until the required memory capacity becomes available in the storage device 102.
The reading operation of an original document is resumed when a margin of memory capacity appears in the storage device 102. When the operation for reading an original document is resumed, the original document on which the reading operation was interrupted is set in the automatic document feeder, and is read after specifying the read operation again. Therefore, the operation may become complicated, depending on the memory capacity remaining in the storage device 102.
The disadvantage described above can be overcome by determining in advance, whether there remains sufficient memory capacity in the storage device 102 for storing, in the compressed state, the total picture image information.
The picture image storing device can readily find the memory capacity remaining in the storage device 102 if the picture image storing device controls the residual memory capacity of the storage device 102. The amount of information on the original document before the compressing process is performed can be determined based upon the resolution when the original document is read by the scanner 100 and the size of the original document. The amount of information after compressing the picture image information will vary among individual original documents as the compression efficiency achieved for each document will vary. Hence, it is not possible to determine in advance the amount of compressed information in any given original document.
The known picture image encoding process discriminates the picture image information, within a given block, on the basis of the parameters m and n. The picture image information within a given block is expressed in terms of the resolution information .PHI..sub.ij and the chromatic gradation information pO, p1, and p2. The picture image information, with the values of .PHI..sub.ij, namely, the resolution information put together for several lines, is encoded by an already known binary value encoding process, and the length in which the blocks having the same information occur in succession is encoded by a known process of run length encoding. Thus, depending on the characteristics of the picture image information within the block discriminated by the parameters m and n, the amount of information in the resolution information .PHI..sub.ij varies, and the chromatic gradation information pO, p1, and p2, which express the picture image information in a given block is different. Moreover, the resolution information .PHI..sub.ij is encoded by a known binary value encoding process and then encoded further by the run length encoding process. Therefore, the amount of encoded picture image information varies depending on the contents of the individual original documents, and determining the amount of the information in any compressed state original document is consequently not possible.
The known picture image encoding process can only express the pixels within a given block in terms of the three chromatic grades in the chromatic gradation information pO, p1, and p2. If an attempt is made at increasing the block size L for the purpose of improving the encoding efficiency, the quality of picture images will deteriorate considerably because the picture image information in a larger area can only be expressed in the three chromatic grades.
In the known picture image encoding process, the resolution information .PHI..sub.ij is allocated uniformly to all the individual pixels in the block, regardless of the characteristics of the picture image information. The uniform resolution allocation increases the redundancy of information.
As described so far, the known picture image storing device cannot determine in advance the amount of information resulting from the compressed picture image information of the original document, and the device, therefore, offers no means of deciding in advance whether or not there remains sufficient memory capacity in the storage device 102 for the storage of the compressed picture image information. Consequently, the operations for the reading of an original document into the system will be complicated. In addition, the quality of the picture images will deteriorate considerably if an attempt is made to increase the block size L for the purpose of improving the encoding efficiency, and the amount information in the block after it is compressed will be redundant.
To overcoming the above disadvantages, the picture image information of an original document may be stored without compression in the storage device 102. Direct storage requires a change in the basic design concept of the picture image storing device. The amount of information in the original document can be found on the basis of the resolution the original document and the size of and number of sheets in the original document. Hence, by comparing the amount of the information in the original document with the memory capacity remaining in the storage device 102, it will be possible to determine in advance whether or not the picture image information of the original document intended for the reading operation can be stored in the storage device 102.
However, the process just described will be required to process an enormous amount of data. A single sheet in an original document in A4 size entered at a resolution of 400 dpi has as much as two mega bytes of information. Therefore, the number of sheets in an original document which can be stored in the storage device 102 will be reduced drastically because of the enormous amount of information to be stored. The non-compression process will not be capable of achieving any practically feasible level of performance in the electronic recirculating document handler function, the book-binding function, and so forth which are required of digital copying machines. On the other hand, if a copying machine were provided with a storage device 102 having a memory capacity sufficiently large to store the picture image information of a large number of sheets in a original document without data compression, the storage device 102 would be very large, and considerable cost increase would be incurred.
In order to store compressed picture image information and determine in advance whether it is possible to store the compressed picture image information in the storage device 102, a new process which measures the ratio of compression in advance of the reading of the original document is performed. An estimated average ratio of compression per original document estimated in advance by a statistical process may also be used.
Specifically, the device which measures the ratio of compression performs a prescanning operation in advance of the regular reading operation. The ratio of compression is thereby measured in advance for the picture image information of the original document. On the basis of the ratio of compression, whether or not there remains sufficient memory capacity in the storage device 102 for the storage of the compressed picture image information is determined.
The prescanning operation must be performed ahead of the reading operation and it is therefore necessary to perform the additional sequential operations and their control for the prescan. Consequently, controlling the copying operations will be more complicated, and the number of copies produced in a unit duration of time decreases in proportion to the time necessary for the prescanning operation and the arithmetic operations incidentally required. In order to prevent a decrease in the number of copies which can be produced in a unit of time, the duration of time spent for the back scan operation is allocated to the prescan. However, the device will not be able to perform any concurrent picture image processing of a number of picture images input from other input devices such as a facsimile machine in the course of the back scan operation.
The other known solution is to provide device which estimates the ratio of compression for an original document in advance by a statistical process. The average ratio of compression estimated for an original document is applied to a process for determining the amount of information, after compression. On the basis of the amount of information thus obtained, whether or not there remains memory capacity in the storage device 102 sufficient for the storage of the compressed picture image information is determined.
The ratio of compression for the original document is only an average ratio of compression estimated by a statistical method. As the applied ratio of compression is different from the actual ratio of compression for the original document, the probability remains that the amount of compressed information actually read from the original document will be in excess of the memory capacity remaining in the storage device 102. The information to be stored may be excessive even if a safety factor is added to the estimated average ratio of compression. In such a case, the picture image information read from the original document will not be stored in the storage device 102, and, consequently, the problem mentioned above will remain unsolved and pending. This probability is associated with the fact that the amount of compressed information increases as the ratio of compression is reduced to a ratio of compression much lower than the average ratio of compression. If picture images in halftone, such as photographs, are included in an original document which is mainly composed of characters when the chromatic gradation information is being processed by an error diffusing method, the estimated compression ratio will be in error.
Furthermore, the device, which operates with the picture image encoding process described above, still suffers from a considerable deterioration in the quality of the picture images and redundancy in the amount of compressed information, if the block size L is enlarged for the purpose of improving the encoding efficiency.